/*
 * @lc app=leetcode.cn id=677 lang=typescript
 *
 * [677] 键值映射
 */

// @lc code=start

class Node677 {
  next: Map<string, Node677>;
  // 当前前缀的所有单词
  words: Set<string>;
  isWord: boolean;
  constructor(word: string = '') {
    this.next = new Map();
    this.words = new Set();
    this.isWord = false;
    if (word) {
      this.words.add(word);
    }
  }

  addWord(word: string) {
    this.words.add(word);
  }
}

class Tire677 {
  root: Node677;
  constructor() {
    this.root = new Node677();
  }

  insert(word: string, val: number) {
    let node: Node677 = this.root;
    for (let i = 0; i < word.length; i++) {
      let c = word[i];
      if (!node.next.has(c)) {
        node.next.set(c, new Node677(word));
      }
      node = node.next.get(c);
      node.addWord(word);
    }
    node.isWord = true;
  }

  search(word: string): Set<string> | null {
    let node: Node677 = this.root;
    for (let i = 0; i < word.length; i++) {
      let c = word[i];
      if (!node.next.has(c)) {
        return null;
      }
      node = node.next.get(c);
    }
    return node.words;
  }
}

class MapSum {
  root: Tire677;
  // 键值映射
  hash: Map<string, number> = new Map();
  constructor() {
    this.root = new Tire677();
  }

  insert(key: string, val: number): void {
    this.hash.set(key, val);
    this.root.insert(key, val);
  }

  sum(prefix: string): number {
    const words = this.root.search(prefix);
    let ans = 0;
    if (words) {
      for (let word of words) {
        ans += this.hash.get(word);
      }
    }
    return ans;
  }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */
// @lc code=end
